{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": "Lesson_8-REVISED.ipynb",
      "provenance": [],
      "collapsed_sections": []
    },
    "language_info": {
      "codemirror_mode": {
        "name": "ipython",
        "version": 3
      },
      "file_extension": ".py",
      "mimetype": "text/x-python",
      "name": "python",
      "nbconvert_exporter": "python",
      "pygments_lexer": "ipython3",
      "version": "3.7.1"
    },
    "kernelspec": {
      "display_name": "Python 3",
      "language": "python",
      "name": "python3"
    }
  },
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "XQgRG9KlCzoP"
      },
      "source": [
        "# Урок 8"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "5bpC3w-ECzoS"
      },
      "source": [
        "# Сингулярное разложение матриц"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "GW7CMC8HCzoU"
      },
      "source": [
        "В данном уроке речь пойдет о разделе линейной алгебры, максимально близком к прикладным вопросам в области машинного обучения, в частности, об одном из самых широко используемых методов разложения матриц. С матричными разложениями вы вскользь знакомились на уроке по линейным преобразованиям и более подробно на уроках по решению СЛАУ."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "n49HHnaTLmhW"
      },
      "source": [
        ""
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "c9uZiQ89CzoW"
      },
      "source": [
        "__Теорема__\n",
        "\n",
        "Для любой ненулевой вещественной матрицы $A$ размером $m\\times n$ существуют две вещественные ортогональные матрицы $U$ и $V$, такие, что $U^{T}AV$ является матрицей $D$ размера $m\\times n$ с неотрицательными элементами на главной диагонали (в прямоугольной матрице под главной диагональю будем понимать совокупность элементов $d_{ii}$). Все элементы матрицы $D$, не лежащие на главной диагонали, являются нулевыми."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "tlWmUSS0CzoX"
      },
      "source": [
        "$U$ и $V$ при этом можно выбрать таким образом, чтобы диагональные элементы матрицы $D$ имели вид\n",
        "\n",
        "$$\\mu_{1}\\geqslant \\mu_{2}\\geqslant ... \\geqslant \\mu_{r} > \\mu_{r+1}=...=\\mu_{n}=0,$$\n",
        "\n",
        "где $r$ — ранг матрицы $A$. В частности, если $A$ невырожденна, то \n",
        "\n",
        "$$\\mu_{1}\\geqslant \\mu_{2}\\geqslant ... \\geqslant \\mu_{r} > 0.$$"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "Bp1aGGQeDMZO"
      },
      "source": [
        ""
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "76gGB5O4CzoZ"
      },
      "source": [
        "Представление матрицы $A$ в виде\n",
        "\n",
        "$$A=UDV^{T}$$\n",
        "\n",
        "называется _сингулярным разложением (Singular Values Decomposition, SVD)_."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "d981617fCzob"
      },
      "source": [
        "Элементы, лежащие на главной диагонали матрицы $D$, называются _сингулярными числами_ матрицы $A$. Столбцы матриц $U$ и $V$ называются _левыми и правыми сингулярными векторами_ матрицы $A$ соответственно."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "8TYMNo6GCzoc"
      },
      "source": [
        "__Геометрический смысл SVD__\n",
        "\n",
        "Пусть матрица $A$ размера $m\\times n$ описывает линейный оператор, обозначаемый $\\textbf{A}$. Сингулярное разложение матрицы $A=UDV^{T}$ тогда можно будет переформулировать в геометрическом контексте: линейный оператор, характеризующий сложное отображение элементов пространства $\\mathbb{R}^{m}$ в элементы пространства $\\mathbb{R}^{n}$, можно будет представить в виде последовательно выполняемых простых линейных операций вращения (ортогональный оператор $U$), растяжения (диагональный оператор $D$) и снова вращения (ортогональный оператор $V^{T}$).\n",
        "\n",
        "Поэтому компоненты сингулярного разложения показывают геометрические изменения при отображении линейным оператором $\\textbf{A}$ векторов из одного линейного пространства в другое.\n",
        "\n",
        "Число ненулевых элементов на диагонали матрицы $D$ будет характеризовать фактическую размерность собственного пространства матрицы $A$ (набора векторов $b$, при котором уравнение $Ax=b$ будет иметь ненулевое решение)."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "P0iF4N4kCzod"
      },
      "source": [
        "### Примеры применения SVD"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "l8v6DckFCzof"
      },
      "source": [
        "__Пример 1__\n",
        "\n",
        "Рассмотрим матрицу $A$, представляющую линейное преобразование $Ax=y$ из одного $n$-мерного пространства, $X$, в другое, $Y$. Предполагаем, что в $X$ и $Y$ заданы ортогональные системы координат. Рассмотрим ортогональное преобразование системы координат в пространстве $X$, в результате которого вектор $x$ получит новое представление $x'$, где $x=Vx'$. Таким же образом, применяя другое ортогональное преобразование координат в $Y$, мы получим новые координаты для $y$, где $y=Uy'$.\n",
        "\n",
        "В результате изменения базисов $X$ и $Y$ преобразование, первоначально представленное матрицей $A$, будет представляться матрицей $D$:\n",
        "\n",
        "$$y'=U^{T}y=U^{T}Ax=U^{T}A(Vx')=(U^{T}AV)x'=Dx'.$$\n",
        "\n",
        "В новой ортогональной системе координат преобразование имеет очень простое представление:\n",
        "\n",
        "$$\\begin{cases}\n",
        "y'_{1}=\\mu_{1}x'_{1},\\\\ \n",
        "y'_{2}=\\mu_{2}x'_{2},\\\\ \n",
        "... \\\\ \n",
        "y'_{r}=\\mu_{r}x'_{r}, \\\\ \n",
        "y'_{r+1}=0, \\\\ \n",
        "... \\\\ \n",
        "y'_{n}=0.\n",
        "\\end{cases}$$\n",
        "\n",
        "Оно теперь отображает координатные оси пространства $X$ с $1$-й до $r$-й в соответствующие координатные оси пространства $Y$, причем $\\mu_{i}>0$ играют роль коэффициентов растяжения. Последующие координатные оси от $(r+1)$ до $n$ отображаются в нулевой вектор пространства $Y$.\n",
        "\n",
        "Таким образом, в данном случае применение SVD значительно упростило работу с линейным преобразованием из одного векторного пространста в другое."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "ldG1fe7FCzog"
      },
      "source": [
        "__Пример 2. Вычисление определителей и нахождение вырожденных матриц__"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "laAjX8nfCzoh"
      },
      "source": [
        "Пусть $A$ — некоторая квадратная матрица. Тогда, имея ее сингулярное разложение, получим\n",
        "\n",
        "$$detA=detU\\cdot detD\\cdot detV^{T}.$$\n",
        "\n",
        "Определитель ортогональной матрицы равен $\\pm1$, а определитель диагональной матрицы есть произведение ее диагональных элементов. Таким образом,\n",
        "\n",
        "$$detA=\\pm \\mu_{1}\\cdot\\mu_{2}\\cdot...\\cdot\\mu_{r}.$$\n",
        "\n",
        "Этот метод бывает полезен, когда имеется матрица $A(z)$, зависящая (возможно, сложным образом) от некоторого параметра $z$, и необходимо найти значения $z$, при которых $detA=0$."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "Dedktw11Czoj"
      },
      "source": [
        "SVD-разложение является удобным методом работы с матрицами и имеет большое количество практических применений, в том числе в алгоритмах машинного обучения и анализе данных. Оно демонстрирует геометрическую структуру матрицы и позволяет наглядно показать данные, имеющиеся в ней. Сингулярное разложение используется при решении самых разнообразных задач — от приближения и вычисления ранга матриц до распознавания изображений и построения рекомендательных систем. "
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "wcsA_BCLCzok"
      },
      "source": [
        "Существует также так называемое сжатое представление сингулярного разложения в случае рассмотрения матрицы размера $m\\times n$. \n",
        "\n",
        "При разложении вида\n",
        "\n",
        "$$A_{(m\\times n)}=U_{(m\\times m)}D_{(m\\times n)}V^{T}_{(n\\times n)}$$\n",
        "\n",
        "в случае $m>n$ матрица $D$ будет иметь пустые строки, а в случае $m<n$ — пустые столбцы. Поэтому разложение можно представить как\n",
        "\n",
        "$$A_{(m\\times n)}=U_{(m\\times r)}D_{(r\\times r)}V^{T}_{(r\\times n)},$$\n",
        "\n",
        "в котором $r=\\text{min}(m,n)$."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "fCf-M0kECzol"
      },
      "source": [
        "### SVD и собственные значения матрицы"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "xnRSubSyK9bt"
      },
      "source": [
        ""
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "8Qi5BdAeCzon"
      },
      "source": [
        "Сингулярное разложение обладает свойством, связывающим задачу нахождения сингулярного разложения матрицы и задачу нахождения ее собственных векторов."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "bephNEWGCzoo"
      },
      "source": [
        "Так как матрицы $U$ и $V$ ортогональные (из чего следует, что $U^{T}U=VV^{T}=E$, где $E$ — единичная матрица порядка $r$) , то \n",
        "\n",
        "$$AA^{T}=UDV^{T}VDU^{T}=UD^{2}U^{T},$$\n",
        "\n",
        "$$A^{T}A=VDU^{T}UDV^{T}=VD^{2}V^{T}.$$"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "oOwUTNidCzoq"
      },
      "source": [
        "Умножив выражения справа на $U$ и $V$ соответственно, получим\n",
        "\n",
        "$$AA^{T}U=UD^{2},$$\n",
        "\n",
        "$$A^{T}AV=VD^{2}.$$"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "zx9fithyCzos"
      },
      "source": [
        "Вспоминая определение собственных векторов и собственных значений, можно заключить, что левые сингулярные векторы матрицы $A$ (столбцы матрицы $U$) являются собственными векторами матрицы $AA^{T}$, а квадраты сингулярных чисел, лежащих на главной диагонали матрицы $D$ — соответствующими собственными значениями этой матрицы.\n",
        "\n",
        "Аналогично правые сингулярные векторы матрицы $A$ (столбцы матрицы $V$) являются собственными векторами матрицы $A^{T}A$, а квадраты сингулярных чисел — ее соответствующими собственными значениями."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "o9GFfnhICzou"
      },
      "source": [
        "Левый и правый сингулярные векторы $u$ и $v$, соответствующие одному и тому же сингулярному числу $\\mu_{j}$, связаны соотношениями\n",
        "\n",
        "$$Av_{j}=\\mu_{j}u_{j}, A^{T}u_{j}=\\mu_{j}v_{j}.$$"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "2FQjf0mVCzow"
      },
      "source": [
        "Существует огромное количество алгоритмов нахождения сингулярного разложения различной производительности и точности, но в данном курсе их рассмотрение не предусмотено. Подробнее о различных алгоритмах нахождения SVD можно прочитать в книге «Матричные вычисления» (п. 2 списка литературы)."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "KUmNGJBfCzoy"
      },
      "source": [
        "В Python сингулярное разложение производится при помощи функции `numpy.linalg.svd(a)`, где `a` — матрица. На выходе она дает три объекта — матрицу $U$, список, состоящий из сингулярных чисел, и матрицу $V^{T}$.\n",
        "\n",
        "\n",
        "Найдем разложение для матрицы \n",
        "\n",
        "$$A=\\begin{pmatrix}\n",
        "0.96 & 1.72\\\\ \n",
        "2.28 & 0.96\n",
        "\\end{pmatrix}.$$"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "VkEG6fJZCzo1"
      },
      "source": [
        "import numpy as np\n",
        "np.set_printoptions(precision=2, suppress=True)"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "rXnJC-oHCzpE",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "0df7d1cc-9e2f-4576-c41b-fbce2bef8652"
      },
      "source": [
        "A = np.array([[0.96, 1.72],\n",
        "              [2.28, 0.96]])\n",
        "print(f'Матрица A:\\n{A}')"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "Матрица A:\n",
            "[[0.96 1.72]\n",
            " [2.28 0.96]]\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "jDJ4H2olCzpS"
      },
      "source": [
        "\n",
        "U, s, W = np.linalg.svd(A)\n",
        "\n",
        "# Транспонируем матрицу W\n",
        "V = W.T\n",
        "\n",
        "# s - список диагональных элементов, его нужно привести к виду диагональной матрицы для наглядности\n",
        "D = np.zeros_like(A, dtype=float)\n",
        "D[np.diag_indices(min(A.shape))] = s"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "bCVxXBkeCzpX",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "4e4feb8f-305b-4b4e-a59b-4e088aa7ef95"
      },
      "source": [
        "print(f'Матрица D:\\n{D}')"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "Матрица D:\n",
            "[[3. 0.]\n",
            " [0. 1.]]\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "SFK1AXYSCzpe",
        "outputId": "3045ea24-3f51-4895-ad13-c8350a2720e8"
      },
      "source": [
        "print(f'Матрица U:\\n{U}')"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "Матрица U:\n",
            "[[-0.6 -0.8]\n",
            " [-0.8  0.6]]\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "Tvvs98MrCzqe",
        "outputId": "4290e069-8ed3-4c51-b517-bfc016cc76be"
      },
      "source": [
        "# Убедимся, что она действительно ортогональна\n",
        "print(np.dot(U.T, U))"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "[[1. 0.]\n",
            " [0. 1.]]\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "mK16DBz-Czqm",
        "outputId": "0f99eb13-a66d-4f58-9a08-bbba10da105b"
      },
      "source": [
        "print(f'Матрица V:\\n{V}')"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "Матрица V:\n",
            "[[-0.8  0.6]\n",
            " [-0.6 -0.8]]\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "VB7oRfoGJ8ho"
      },
      "source": [
        ""
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "S82LygdpCzqt",
        "outputId": "e46ea501-dc08-424e-ecd2-e867d6757675"
      },
      "source": [
        "# Убедимся, что она действительно ортогональна\n",
        "print(np.dot(V.T, V))"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "[[ 1. -0.]\n",
            " [-0.  1.]]\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "y7vNuHHACzq0",
        "outputId": "3810d804-963a-41f3-f43a-02f0e816fa17"
      },
      "source": [
        "# Проведем проверку\n",
        "print(np.dot(np.dot(U, D), V.T))"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "[[0.96 1.72]\n",
            " [2.28 0.96]]\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "_tyVHbGsCzrF"
      },
      "source": [
        "## SVD и нормирование матриц"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "sZkHZOdTCzrH"
      },
      "source": [
        "При умножении ненулевого вектора $x$ на матрицу $A$ норма (длина) получающегося вектора $Ax$ изменяется (если только матрица $A$ не ортогональна, тогда длина вектора остается неизменной), и, посчитав соотношение $\\frac{\\left \\| Ax \\right \\|}{\\left \\| x \\right \\|}$, можно узнать, во сколько раз. Это и будет _евклидова норма матрицы_ — максимальный коэффициент растяжения вектора, то есть она характеризует «значимость» матрицы.\n",
        "\n",
        "$$\\left \\| A \\right \\|_{E}=\\text{max}\\left (\\frac{\\left \\| Ax \\right \\|}{\\left \\| x \\right \\|}\\right )$$"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "MEGAOBTRCzrJ"
      },
      "source": [
        "Как мы помним, евклидова норма вектора определена как\n",
        "\n",
        "$$\\left\\|x\\right\\|_{2} = \\sqrt{\\sum_{i}|x_{i}|^{2}},$$\n",
        "\n",
        "что можно представить также с использованием скалярного произведения\n",
        "\n",
        "$$\\left\\|x\\right\\|_{2}^{2} = (x,x).$$"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "QX8dT-yxCzrm"
      },
      "source": [
        "Осуществим сингулярное разложение матрицы $A=UDV^{T}$ и подставим его в выражение определения нормы, принимая во внимание, что ортогональные матрицы сохраняют скалярное произведение:\n",
        "\n",
        "$$\\left \\| A \\right \\|_{E}^{2}=\\text{max}\\left (\\frac{(Ax,Ax)}{(x,x)}\\right )=\\text{max}\\left (\\frac{(UDV^{T}x,UDV^{T}x)}{(V^{T}x,V^{T}x)}\\right )=\\text{max}\\left (\\frac{(Dz,Dz)}{(z,z)}\\right ).$$\n",
        "\n",
        "Таким образом, евклидова норма матрицы равна евклидовой норме диагональной матрицы из ее сингулярных чисел $D$. Максимальное значение полученного отношения будет равно максимальному сингулярному числу $\\mu_{max}$, и, принимая во внимание факт сортировки по убыванию сингулярных чисел, получим\n",
        "\n",
        "$$\\left \\| A \\right \\|_{E}=\\mu_{1}.$$"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "_0obBUO7Czry"
      },
      "source": [
        "Также существует _норма Фробениуса_, определяемая как\n",
        "\n",
        "$$\\left \\| A \\right \\|_{F}=\\sqrt{\\sum_{i=1}^{m}\\sum_{j=1}^{n}a_{ij}^{2}}.$$"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "Pd2mgUPqCzr0"
      },
      "source": [
        "В случае, когда известно сингулярное разложение матрицы, ее норма Фробениуса вычисляется как\n",
        "\n",
        "$$\\left \\| A \\right \\|_{F}=\\sqrt{\\sum_{k=1}^{r}\\mu_{k}^{2}}.$$"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "1shChDs9CzsF"
      },
      "source": [
        "## Сингулярное разложение в применении к приближению матрицей меньшего ранга"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "nJzS3Je2CzsK"
      },
      "source": [
        "### Идея приближения матрицей меньшего ранга"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "vW6jyDoxCzsM"
      },
      "source": [
        "На практике данные для обработки в большинстве случаев поступают с определенным уровнем шума, в связи с чем не вся информация, содержащаяся в матрице, представляет для анализатора ценность. Таким образом, имеет место задача о нахождении лучшей аппроксимации исходной матрицы $X$ размера $m\\times n$ и ранга $r$ некоторой матрицей, ранг которой не превышает заданное число $k$.\n",
        "\n",
        "Матрица может быть представлена как произведение двух матриц (обозначим его как $UV^{T}$, где $U$ имеет размер $m\\times k$, $V$ — $n\\times k$)."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "eXLLJD1FCzsR"
      },
      "source": [
        "В случае задачи приближения все сводится к тому, чтобы найти такие матрицы $U$ и $V$, чтобы исходная матрица $X$ и матрица $UV^{T}$ отличались незначительно. Для оценки степени «близости» матриц обычно используется норма Фробениуса, и задача поиска оптимального разложения сводится к нахождению комбинации $U$ и $V$, дающей минимальную норму разности $\\left \\| X - UV^{T} \\right \\|$.\n",
        "\n",
        "Другими словами, задача сводится к нахождению матриц $U$ и $V$, удовлетворяющих условию\n",
        "\n",
        "$$\\sum_{ij}(x_{ij}-u_{i}v_{j}^{T})^{2}\\rightarrow\\text{min}.$$"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "fm83EzwqCzsT"
      },
      "source": [
        "Если исходная матрица $X$ была матрицей признаков объектов, то после такого преобразования матрица $U$ может быть интерпретирована как матрица новых признаков для тех же объектов, при этом происходит уменьшение размерности пространства признаков с минимальными потерями полезной информации."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "x0Jn0COQCzsc"
      },
      "source": [
        "### Использование SVD"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "UD3IrlD0Czsd"
      },
      "source": [
        "Пусть для исходной матрицы $X$ требуется найти такую матрицу $\\tilde{X}$ с рангом, не превышающим заданное число $k$, которая наилучшим образом приблизит исходную, то есть норма их разности $\\left \\| X - \\tilde{X} \\right \\|$ будет минимальной."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "ip-7pJp1Czsk"
      },
      "source": [
        "Сингулярное разложение для исходной матрицы будет иметь вид\n",
        "\n",
        "$$X=UDV^{T}.$$\n",
        "\n",
        "Искомую матрицу $\\tilde{X}$ также запишем в виде разложения\n",
        "\n",
        "$$\\tilde{X}=U\\tilde{D}V^{T},$$\n",
        "\n",
        "где $U$ и $V$ — те же, что и в сингулярном разложении матрицы $X$, а матрица $\\tilde{D}$ произвольная, удовлетворяющая условию тождественности преобразования (не обязательно диагональная)."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "tBWNYjn-Czsl"
      },
      "source": [
        "Тогда задача примет вид нахождения минимума нормы разности матриц $\\left \\| D - \\tilde{D} \\right \\|$ рангом не выше $k$.\n",
        "\n",
        "Поскольку все недиагональные элементы в матрице $D$ равны нулю, условие минимума разности приводит к тому, что недиагональные элементы в матрице $\\tilde{D}$ также должны быть равными нулю. Если она диагональная, то, по условию непревышения ранга матрицы $\\tilde{X}$ числа $k$, в ней должно быть максимум $k$ ненулевых элементов. Наиболее оптимальным в плане минимализации $\\left \\| D - \\tilde{D} \\right \\|$ будет выбор $\\tilde{D}$ равного матрице $D$, в которой все элементы, кроме $k$ наибольших по модулю, заменены нулями.\n",
        "\n",
        "Таким образом, лучшим приближением матрицы $X$ будет матрица \n",
        "\n",
        "$$\\tilde{X}=U\\tilde{D}V^{T},$$\n",
        "\n",
        "где матрица $\\tilde{D}$ — это матрица $D$, в которой все элементы, кроме $k$ наибольших по модулю, заменены нулями."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "vrNYoQugCzsm"
      },
      "source": [
        "Таким образом, задавая явно число $k$, можно регулировать точность приближения исходной матрицы новой матрицей пониженной размерности."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "88Mbd_tGCzso"
      },
      "source": [
        "## Практическое задание"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "aoo5c_Q0Czsp"
      },
      "source": [
        "1. Найти с помощью NumPy SVD для матрицы\n",
        "\n",
        "$$\\begin{pmatrix}\n",
        "1 & 2 & 0\\\\ \n",
        "0 & 0 & 5\\\\ \n",
        "3 & -4 & 2\\\\ \n",
        "1 & 6 & 5\\\\ \n",
        "0 & 1 & 0\n",
        "\\end{pmatrix}.$$\n",
        "\n",
        "\n",
        "2. Для матрицы из предыдущего задания найти:\n",
        "\n",
        "    а) евклидову норму;\n",
        "    \n",
        "    б) норму Фробениуса."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "BvECW7ca8kMd"
      },
      "source": [
        "## Литература"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "LnletOum8lPV"
      },
      "source": [
        " 1. Форсайт Дж., Молер К. Численное решение систем линейных алгебраических\n",
        "уравнений. М.: Мир, 1969.\n",
        " 2. Форсайт Дж., Малькольм М., Моулер К. Машинные методы математических\n",
        "вычислений. М.: Мир, 1980.\n",
        " 3. Голуб Дж., Ван-Лоун Ч. Матричные вычисления. М.: Мир, 1999.\n",
        " 4. Логинов Н. В. Сингулярное разложение матриц. М.: Мир, 1996.\n",
        " 5. Хорн Р., Джонсон Ч. Матричный анализ. М.: Мир, 1989."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "3Ht4c166Czsu"
      },
      "source": [
        "1. [SVD в NumPy](https://docs.scipy.org/doc/numpy-1.15.1/reference/generated/numpy.linalg.svd.html)."
      ]
    }
  ]
}